Problem

Time limit : 2sec / Memory limit : 256MB

题意：

给定一个数组，求有多少个子序列满足$\displaystyle A_l \oplus A_{l+1} \oplus \dots\oplus A_r=\sum_{i=l}^{r} A_i$

door♂

Solution

尺取法。

根据题意得到：

对于一段连续子序列，如果在$a_i$这个数不符合公式的话，即之后的符合条件的对数中将不再需要这个元素
枚举元素来计算符合公式的对数
记$\text{sum}$为异或和，我们有$\text{sum}_r \oplus \text{sum}_{l-1}=\text{sum}_l \oplus \text{sum}_{l+1}………\oplus \text{sum}_r$

Code:

Click to show/hide the code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
long long f[maxn], s[maxn];
long long ans;
int n, x;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
    	cin >> x;
        f[i] = f[i-1] + x;
        s[i] = s[i-1] ^ x;
    }
    int l = 1;
    ans = 0;
    for (int r = 1; r <= n; r++)
    {
        for(; f[r] - f[l-1] != (s[r] ^ s[l-1]); l++);
        ans += r - l + 1;
    }
    cout << ans;
    return 0;
}

这个ios::sync_with_stdio(false);真的有毒，就因为最后一个printf没改成cout然后就一直WA…..mmp